package com.lzh.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author liuzhihao
 * @create 2022-01-24 21:01
 * 选择排序
 */
public class SelectSort {

    public static void main(String[] args) {

        int[] arr = {101, 34, 119, 1};

        int[] arr2 = new int[80000];
        for (int i = 0; i < arr2.length; i++) {
            arr2[i] = (int) (Math.random() * 80000);
        }

        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(date1);
        System.out.println("排序前的时间：" + date1Str);

        selectSort(arr2);

        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间：" + date2Str);

//        System.out.println("排序后");
//        System.out.println(Arrays.toString(arr));

    }

    // 选择排序
    public static void selectSort(int[] arr) {

        // 在推导的过程中，我们发现了规律，可以使用一个for循环来解决
        // 选择排序的时间复杂度为O(n^2)
        for (int i=0; i < arr.length-1; i++) {
            int minIndex = i;
            int min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < min) { // 说明假设的这个最小值并不是最小值
                    min = arr[j]; // 重置min
                    minIndex = j; // 重置minIndex
                }
            }

            // 将最小值，放在arr[0]这个位置，即交换
            if (minIndex !=i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }

//            System.out.println("第"+(i + 1)+"轮~~");
//            System.out.println(Arrays.toString(arr));
        }



//        // 使用逐步推导的方式来，讲解选择排序
//
//        // 第一轮
//        // 原始数组： 101， 34 ， 119， 1
//        // 第一轮：   1 ， 34， 119， 101
//        // 算法 先简单 ---》 复杂, 可以把一个复杂的算法，拆分成简单的问题 -》逐步解决
//
//        // 第一轮
//        int minIndex = 0;
//        int min = arr[minIndex];
//        for (int i = 1; i < arr.length; i++) {
//            if (arr[i] < min) { // 说明假设的这个最小值并不是最小值
//                min = arr[i]; // 重置min
//                minIndex = i; // 重置minIndex
//            }
//        }
//
//        // 将最小值，放在arr[0]这个位置，即交换
//        if (minIndex !=0) {
//            arr[minIndex] = arr[0];
//            arr[0] = min;
//        }
//
//        System.out.println("第一轮~~");
//        System.out.println(Arrays.toString(arr));
//
//
//        // 第二轮
//        minIndex = 1;
//        min = arr[1];
//        for (int i = 2; i < arr.length; i++) {
//            if (arr[i] < min) { // 说明假设的这个最小值并不是最小值
//                min = arr[i]; // 重置min
//                minIndex = i; // 重置minIndex
//            }
//        }
//
//        // 将最小值，放在arr[0]这个位置，即交换
//        if (minIndex != 1) {
//            arr[minIndex] = arr[1];
//            arr[1] = min;
//        }
//
//        System.out.println("第二轮~~");
//        System.out.println(Arrays.toString(arr));
//
//        // 第二轮
//        minIndex = 2;
//        min = arr[2];
//        for (int i = 3;i < arr.length; i++) {
//            if (arr[i] < min) { // 说明假设的这个最小值并不是最小值
//                min = arr[i]; // 重置min
//                minIndex = i; // 重置minIndex
//            }
//        }
//
//        // 将最小值，放在arr[0]这个位置，即交换
//        if (minIndex != 2) {
//            arr[minIndex] = arr[2];
//            arr[2] = min;
//        }
//
//        System.out.println("第三轮~~");
//        System.out.println(Arrays.toString(arr));
    }

}
